package leetcode;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2022/3/3
 * Time:10:19
 */
public class 打家劫舍II {
    public static void main(String[] args) {
        int[] nums = {1,2,3,1};
        System.out.println(rob(nums));
    }
    public static int rob(int[] nums) {
        int len = nums.length;
        if(len < 2) return nums[0];
        if(len == 2) return Math.max(nums[0],nums[1]);
        return Math.max(robber(nums,len-1,0),robber(nums,len,1));
    }

    public static int robber(int[] nums,int len,int start){
        int[] dp = new int[nums.length-1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start],nums[start+1]);
        for(int i = 2;i<len;i++){
            dp[i] = Math.max(dp[i - 1],dp[i-2]+nums[i]);
        }
        return dp[dp.length-1];
    }
}
